1. Field of the Invention
The present invention relates generally to information processing systems for representing objects in three dimensions. The present invention relates more specifically to systems which use boundary representations (BREPs) to represent objects in a non-manifold environment.
2. Description of the Prior Art
Modeling of objects in three dimensions using information processing systems has many applications. For example, software models are used during the design of mechanical parts. Testing a model of a part for parameters such as correct fit is usually much less expensive than testing an actual part. Another important purpose of modeling is to obtain a visual image of a part under design. Thus, a number of modeling technologies have been developed and optimized for determining various parameters of a modeled part and for providing visual images of a modeled part.
There are two ways of representing complex information, such as that contained in a solid model, explicitly and implicitly. In an explicit representation, operations called for by the input data are fully resolved. Thus, the representation contains only the final result of those operations called for by the input data. In contrast, in an implicit representation, relationships between the input data are not fully resolved; in fact, they may not be resolved at all. Thus, an implicit representation contains representations of both data and operations to be performed on them.
One approach to solid modeling, known as Constructive Solid Geometry (CSG), creates an implicit representation of a complex solid, as a collection of primitive solids and operations for combining them. This representation of a complex solid in CSG is implicit, because the operations by which the primitive solids are combined to form a complex solid are not resolved. Thus, for example, if a hole "drilled" through a cube is desired, the resulting CSG model (as illustrated in FIG. 1a) contains information about both the entire volume of the cube 101 and the cylinder 103 used to "drill" the hole (i.e., the volume where the cylinder 103 coincides with the cube 101 is subtracted), as well as the operation performed (volumetric subtraction, in this case). Extraneous information, such as a specification of those portions of the cylinder 103 which may extend beyond the boundaries of the cube 101 are also retained in a database holding the model.
Complex objects are formed by performing Boolean operations on two or more primitive solids. These operations include, but are not limited to volumetric union, volumetric intersection and volumetric subtraction. By applying Boolean operations to an aggregation of primitive solids, a variety of complex solid objects may be represented. For example, subtracting a cylinder from a cube produces a cube having a hole drilled in it like that of FIG. 1a. The Boolean operations which may be performed on primitive solids represent the range of operations used while designing a part.
In CSG, a complex solid is typically represented as a tree data structure. The data stored in the tree data structure includes a set of primitives and a set of Boolean operations which are performed on the primitives. A simple example of such a tree data structure is illustrated in FIG. 1b, for the solid shown in FIG. 1a. The CSG tree data structure for this solid model comprises data storage nodes of two types, interior nodes 105 and leaf nodes 107a and 107b. The leaf nodes 107a and 107b represent primitive solids 101 and 103. The interior node 105 specifies a Boolean operation 109 to be performed, in this case a Boolean subtraction, and includes data pointing 111a and 111b to leaf nodes 107a and 107b upon which the Boolean operation 109 is performed.
Since a CSG model does not include an explicit representation of the complex solid being modeled, the data structure is evaluated for display when a visual image is requested. This is difficult and time-consuming. Furthermore, matters are made worse since the evaluation is performed each time a change is made to the data structure.
A second approach to solid modeling, Boundary Representation (BREP), creates an explicit representation of a complex solid in the form of geometric shape information and topological information. The geometric shape information includes information such as volumes, surfaces, curves and points. The topological information corresponds to the respective geometric information. Hence, information such as a specification of regions, faces, edges and vertices is included in the topological information. Two additional topological entities, loops and shells, are used in representations of holes in faces and voids in regions, respectively.
In a boundary representation, the data structure used to hold a complex solid model is a connected graph of the topological entities of the complex solid model. Thus, useful adjacency relationships may be derived from the graph of the topology data structure, or those relationships may be explicitly stored within the data structure.
A drawback of the boundary representation approach of the prior art is that modification of a model stored as an explicit representation of a desired solid is difficult. Making even minor changes to a model frequently involves performing a boundary evaluation of a complete CSG representation of the model. Boundary evaluation is a process of creating or maintaining a boundary representation equivalent of a CSG representation of an object. A further drawback of the prior art stems from the reliance on manifold structures in the prior art, as explained below.
In the context of solid modeling, the term manifold is commonly used as an abbreviation of the term two-manifold, meaning "locally two-dimensional." That is, on the boundary of a manifold solid, for example as shown in FIG. 2a, the small area around any point 201 is "locally two-dimensional," or homomorphic to a disk (i.e., there is a 1--1 mapping of the points of a small region of a manifold solid to the points of the disk). Thus, the small area around any point, such as the area in section IIb, has a direct correspondence with the disk and may be squashed flat, as illustrated in FIG. 2b, without leaving any protruding features and without requiring the laying of one feature on top of another. This is contrasted with the same test applied to section IIIb of FIG. 3a showing a non-manifold (i.e., not two-manifold) topology. Wire 301 protruding from point 303 cannot be squashed flat without overlaying some of the surrounding surface 305, as shown in FIG. 3b. Thus, wire 301 does not have a direct correspondence with any part of the disk not already occupied by the surrounding surface 305. Solid modelers of the prior art store adjacency data of boundary representations as manifold topological representations or only permit a limited subset of non-manifold conditions to be stored as special cases.
However, modeling solids in a manifold environment is inadequate, since simple operations on manifold objects may produce non-manifold objects. Mathematically speaking, the set of Boolean operations is not closed over the set of manifold solids. For example, performing the union of two boxes oriented in space to share a common edge produces an object which is non-manifold at any point along the shared edge. Thus, another problem in the prior art is that manifold-based solid modelers either give up some adjacency data wherever a non-manifold condition occurs, or treat the non-manifold condition as a special case, or else simply fail to perform the required operation. Since many important constructions are non-manifold, the inability to handle non-manifold conditions is an important deficiency of manifold modelers of the prior art.
Therefore, it is an object of the present invention to provide a method and apparatus for performing boundary evaluation of boundary representation models having non-manifold topologies.
Another object of the present invention is to provide a method and apparatus that performs boundary evaluation of non-manifold boundary representation models without resorting to special cases to represent the information inherent in non-manifold topologies.
Another object of the present invention is to provide a general method and apparatus that performs local modification of an explicit boundary representation reflecting modifications to a corresponding implicit CSG representation without resorting to a complete rederivation of the boundary representation from the CSG representation.